{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "9ae15733",
   "metadata": {},
   "source": [
    "https://blog.csdn.net/juzihongle1/article/details/73135920"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dd08e6a6",
   "metadata": {},
   "source": [
    "1.Recursive backtracker ( 递归回溯，也是深度优先算法）\n",
    "\n",
    "2.Randomized Prim's algorithm（随机Prim算法，让我想起了最小生成树的Prim算法）\n",
    "\n",
    "3.Recursive division （递归分割算法）\n",
    "\n",
    "首先，为了方便后续处理，默认的迷宫元素表示为[x,y,w]：\n",
    "\n",
    "1.我们的迷宫为常规的矩形，因此可以用二维表示一个迷宫单元, 每个迷宫单元表示为一个二维数组元素[x,y]。\n",
    "\n",
    "3.每个迷宫单元包含左上右下四个属性, 用w表示，分别表示迷宫单元四个面的墙，墙不占据迷宫单元。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12b2ee48",
   "metadata": {},
   "source": [
    "深度优先构建迷宫的思想就是，每次把新找到的未访问迷宫单元作为优先，寻找其相邻的未访问过的迷宫单元，直到所有的单元都被访问到。通俗的说，就是从起点开始随机走，走不通了就返回上一步，从下一个能走的地方再开始随机走。一般来说，深度优先法生成的迷宫极度扭曲，有着一条明显的主路。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "d50f7307",
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "73d9b1cd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Rows: 20\n",
      "Columns: 20\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAQEAAAD8CAYAAAB3lxGOAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAART0lEQVR4nO3dUawc1X3H8e+vpiA1RQoUcF0gxSATCaPqtrHIAwKRtgkkSmuoRGpURVaCYpDwQ6U+FKjUoPQlaiGoUhsko1g4UsFYqghWRAKuH4L6QMFOEDEQBxscuNiyAzQlbaQgm38fdq5Yrvfeu7szZ+bMnt9Hurq75+7O/M/M+u8zZ86eo4jAzMr1G10HYGbdchIwK5yTgFnhnATMCuckYFY4JwGzwiVLApJukHRQ0iFJd6baj5nVoxTjBCStAn4KfBqYB54DbomIlxrfmZnVkqolcBVwKCJejYj3gJ3AxkT7MrMazki03QuBN4aezwOfXOrFkjxs0Sy9tyLi/MWFqZKARpR96B+6pC3AlkT7N7PT/WxUYaokMA9cPPT8IuDo8AsiYhuwDWDDhg2xb9++xnYufTgHNdHvsXibTW3XJpfi/KaSQ6yjPrvDUvUJPAesk7RW0pnAJmB3on2ZWQ1JWgIRcVLSVuBJYBWwPSJeTLEvM6sn1eUAEfEE8ESq7ZtZMzxi0KxwTgJmhXMSMCtckmHDEwcxxWCh5eKe5LbMuK+d5BbhSrdkbGWTnLMmtlv3nHX9WRjzeO2PiA2L/+6WgFnhnATMCuckYFa4ZOMEppFD/0QqKYYu5zAEtakYUlzn19XEdifZRlfn1y0Bs8I5CZgVzknArHBOAmaFcxIwK5yTgFnhsrpFuJxZHYqbasaitm65TbKftm9p1v3MpPjMpbqlWme7bgmYFc5JwKxwTgJmhZu6T0DSxcC3gd8F3ge2RcQ/S7oH+Arw8+qld1dTjTWq7evLHIY014kh56G1bcp55umujmWdjsGTwN9ExA8lnQ3sl7Sn+tv9EXFv/fDMLLWpk0BEHAOOVY9/KellBisPmVmPNNInIOkS4A+B/6qKtkp6QdJ2Sec0sQ8zS6N2EpD028C/A38dEe8CDwCXAXMMWgr3LfG+LZL2SWpu6SEzm1itOQYl/SbwXeDJiPjGiL9fAnw3Iq5cYTsBzc0bOImulyxra7BQzsdr0u2mmBdyEjksSTfl8Wp2jkENtvwt4OXhBCBpzdDLbgIOTLsPM0uvzt2Bq4EvAj+W9HxVdjdwi6Q5BqsQHwFuq7GPqdQZ7pnD8OQUMXQxvDeHYzmuuv+7d13XOvuvc3fgPxm9BLmXHjPrEY8YNCuck4BZ4XrzVeJJpJjhddaGig5rq78gh7qm0qc7Oou5JWBWOCcBs8I5CZgVzknArHBOAmaFm8m7A12v2df16LFRch/9luMxa0IO37VYiVsCZoVzEjArnJOAWeGcBMwKN5MdgynU7dDJuXMyVWypVkEad7t9m2G5q2HVbgmYFc5JwKxwTgJmhXMSMCuck4BZ4WrdHZB0BPglcAo4GREbJJ0LPApcwmCi0S9ExH/XC3PkvpveZNL9NdFbn+MEqjlPFNLmOetym3U10RL4VETMDc1nfiewNyLWAXur52aWqRSXAxuBHdXjHcCNCfZhZg2pmwQCeErSfklbqrLV1WKlC4uWXjDqjV6GzCwPdUcMXh0RRyVdAOyR9JNx3xgR24Bt8MEyZGbWvlpJICKOVr9PSHoMuAo4LmlNRByrliQ70UCco/adYrON7K+ttepy7pRLadx653B8uppBeBJ11iL8iKSzFx4Dn2Gw7uBuYHP1ss3A43WDNLN06rQEVgOPVRnpDODhiPi+pOeAXZJuBV4Hbq4fppmlUmtp8saCKHhp8jrbzeHcLSfFcuN9k8PnNtnS5GY2G5wEzAo3k5OKtDW8tk+XDpNoYkKPlHKIIYWuLoncEjArnJOAWeGcBMwK5yRgVriZ7BhcrO2Othzvcafq7MuhrrPaQdsWtwTMCuckYFY4JwGzwjkJmBXOScCscEXcHVhOjjP4zoquj22bPf453CWZllsCZoVzEjArnJOAWeGK7xNIcS3Xt2vGVLHlXOe29OHYTp0EJH2cwXJjCy4F/h74KPAV4OdV+d0R8cS0+zGztBqZY1DSKuBN4JPAl4D/jYh7J3h/o3MMdj1fXQ5zDOYwt13XJjkPqV47iRbOWdI5Bv8EOBwRP2toe2bWkqaSwCbgkaHnWyW9IGm7pHNGvcHLkJnlofblgKQzgaPA+og4Lmk18BaDdQr/AVgTEV9eYRu+HJhiu74cWJ4vB07bbrLLgc8CP4yI4wARcTwiTkXE+8CDDJYmM7NMNXGL8BaGLgUW1iGsnt7EYGmybI2bfVMNEW5r6HHf489diuPQ1kQ2tZKApN8CPg3cNlT8j5LmGFwOHFn0NzPLTN1ViX8F/M6isi/WisjMWuVhw2aF682w4Rx7odseEtr3CUHb1mZ/Rc53B1biloBZ4ZwEzArnJGBWOCcBs8I5CZgVzknArHBZ3SKclSGofatH3+JdLIfbn+Mew1Rf5KrDLQGzwjkJmBXOScCscFn1CeQ8Ucgk+8vhGnUSOcRbZ8KUtk1yvNr6OnCd4+WWgFnhnATMCuckYFY4JwGzwjkJmBVuxSRQrR1wQtKBobJzJe2R9Er1+5yhv90l6ZCkg5KuTxW4mTVjnJbAQ8ANi8ruBPZGxDpgb/UcSVcwWIhkffWeb1ZLlLVK0tg/dd7b9k9bxyTH+HOSqm5dHcsVk0BEPA28s6h4I7CjerwDuHGofGdE/DoiXgMO4XUHzLI2bZ/A6oW1BarfF1TlFwJvDL1uviozs0w1PWJwVDtl5FAmSVuALQ3v38wmNG0SOK5qpSFJa4ATVfk8cPHQ6y5isE7haSJiG7ANPliLcDmphlSOa9R1WA7DbZeSQ2xd9wPkcAwm0VW8014O7AY2V483A48PlW+SdJaktcA64Nl6IZpZSiu2BCQ9AlwHnCdpHvgq8HVgl6RbgdeBmwEi4kVJu4CXgJPAHRFxKlHsZtaA2kuTNxLEGEuTT7i9Dz0v8XIgB5Och1SvHdck57fOa7v4zAzFkGxpcjPrMScBs8I5CZgVLquZhZaT6nZTW9eXlk6fjneqWOt8bt0SMCuck4BZ4ZwEzArXmz6BPt2TrzsbbYp+iZzHYEwqxT5zvFZfTpPxuiVgVjgnAbPCOQmYFc5JwKxwTgJmhXMSMCtcVrcI+zT8E9pbbHKp/eV+26/O+Wzi2Lb5eUqxr7Zuv7olYFY4JwGzwjkJmBVunDkGtwOfB05ExJVV2T8Bfwa8BxwGvhQRv5B0CfAycLB6+zMRcfu4weQ8NLjuUOAmtpuDrmd9ritVDH3+Cvq0y5DtAa6MiD8AfgrcNfS3wxExV/2MnQDMrBtTLUMWEU9FxMnq6TMM1hcwsx5qok/gy8D3hp6vlfQjST+QdE0D2zezhGqNE5D0dwzWF/i3qugY8LGIeFvSJ4DvSFofEe+OeK+XITPLwNQtAUmbGXQY/lVUvSLVasRvV4/3M+g0vHzU+yNiW0RsGDUPupm1Z6okIOkG4G+BP4+IXw2Vny9pVfX4UgbLkL3aRKBmlsa0y5DdBZwF7KluayzcCrwW+Jqkk8Ap4PaIeGfkhifUtyHFi/Up/rZmdl7OJCsQNaFPs1k3rTfLkPXpH1FbUi3rlYNU8ab6nkETy5C18FovQ2Zmp3MSMCtcVl8lXk5bs7bmcHnUtY5Xzl1RW/GV8llwS8CscE4CZoVzEjArnJOAWeGcBMwKl9XdgZzXg2trMEnuUgzUaXo/qeUc2zTcEjArnJOAWeGcBMwK5yRgVrisOgb7Nkwz55lr29LUt/3qdBrmcLya6Pjtqh5uCZgVzknArHBOAmaFcxIwK9yKSUDSdkknJB0YKrtH0puSnq9+Pjf0t7skHZJ0UNL1qQI3s2aMc3fgIeBfgG8vKr8/Iu4dLpB0BbAJWA/8HvAfki6PiFN1A81xqGbbMeV4DCbRdk95jscrx5imWoZsGRuBndX6A68Bh4CrasRnZonV6RPYKumF6nLhnKrsQuCNodfMV2Vmlqlpk8ADwGXAHIOlx+6ryke1dUa26yRtkbRP0r4pYzCzBkyVBCLieEScioj3gQf5oMk/D1w89NKLgKNLbMPLkJllYKphw5LWRMSx6ulNwMKdg93Aw5K+waBjcB3wbO0oR2hqiOW4HTVtzXbcRQyppJo/oM5xmGR4bxPHuw/Doaddhuw6SXMMmvpHgNsAIuJFSbuAlxisVnxHE3cGzCyd3i5Dlqol0PbxSPU/UCp9Og+THNsczkMLx9bLkJnZ6ZwEzArnJGBWuKwmFWlqSGWda6smeqnrXl/mOLR0Gm2dh7a1NeNyqhgWc0vArHBOAmaFcxIwK5yTgFnhsuoY7GKQzLj7zHmJtLq6HjDV1T6b1PVsw3VmfXZLwKxwTgJmhXMSMCuck4BZ4ZwEzAqX1d2B5dTpnW9rTbzUMeQ4XDWHocApjlcqOcbkloBZ4ZwEzArnJGBWuHHmGNwOfB44ERFXVmWPAh+vXvJR4BcRMSfpEuBl4GD1t2ci4vYmAu16os8cR7TlGNNycoi37Ri6/tyOY6plyCLiL4eCuQ/4n6HXH46IuYbiM7PEVkwCEfF09T/8aTRIR18A/rjhuMysJXX7BK4BjkfEK0NlayX9SNIPJF1Tc/tmlljdcQK3AI8MPT8GfCwi3pb0CeA7ktZHxLuL3yhpC7Cl5v7NrKapWwKSzgD+Anh0oaxajfjt6vF+4DBw+aj3exkyszzUuRz4U+AnETG/UCDpfEmrqseXMliG7NV6IZpZSlMtQxYR3wI28eFLAYBrga9JOgmcAm6PiHeaCLStIbNdD++dRI5DUJfT1PDtFPVOdSxzGOq9kt4uQzaJtrfbt3+cizW1HFxJ56zt73tMeR68DJmZnc5JwKxwvfkqcddr3adqLqbSt8lDSzlnbfd1jMMtAbPCOQmYFc5JwKxwTgJmhXMSMCuck4BZ4bK6RZjDrMBtz56bw7DSvs/k3LacY5uGWwJmhXMSMCuck4BZ4bLqE2jqGjfFtWeqYbc59G3kMCNu199mrbv/JuJPdc4WXrvU+XBLwKxwTgJmhXMSMCuck4BZ4ZwEzArnJGBWuKxuEeYwHDOHGMbVp1ihf/FOos91c0vArHC5tATeAv6v+j1rzmM26wWzW7dZrdfvjyrMYt0BAEn7ZnFJslmtF8xu3Wa1Xkvx5YBZ4ZwEzAqXUxLY1nUAicxqvWB26zar9Ropmz4BM+tGTi0BM+tA50lA0g2SDko6JOnOruOpS9IRST+W9LykfVXZuZL2SHql+n1O13GuRNJ2SSckHRgqW7Ieku6qzuFBSdd3E/V4lqjbPZLerM7b85I+N/S33tRtGp0mAUmrgH8FPgtcAdwi6YouY2rIpyJibug2053A3ohYB+ytnufuIeCGRWUj61Gds03A+uo936zOba4e4vS6Adxfnbe5iHgCelm3iXXdErgKOBQRr0bEe8BOYGPHMaWwEdhRPd4B3NhdKOOJiKeBdxYVL1WPjcDOiPh1RLwGHGJwbrO0RN2W0qu6TaPrJHAh8MbQ8/mqrM8CeErSfklbqrLVEXEMoPp9QWfR1bNUPWblPG6V9EJ1ubBwqTMrdVtS10lg1Lcu+n674uqI+CMGlzh3SLq264BaMAvn8QHgMmAOOAbcV5XPQt2W1XUSmAcuHnp+EXC0o1gaERFHq98ngMcYNB2PS1oDUP0+0V2EtSxVj96fx4g4HhGnIuJ94EE+aPL3vm4r6ToJPAesk7RW0pkMOmB2dxzT1CR9RNLZC4+BzwAHGNRpc/WyzcDj3URY21L12A1sknSWpLXAOuDZDuKb2kJyq9zE4LzBDNRtJZ1+izAiTkraCjwJrAK2R8SLXcZU02rgseq75WcAD0fE9yU9B+ySdCvwOnBzhzGORdIjwHXAeZLmga8CX2dEPSLiRUm7gJeAk8AdEXGqk8DHsETdrpM0x6CpfwS4DfpXt2l4xKBZ4bq+HDCzjjkJmBXOScCscE4CZoVzEjArnJOAWeGcBMwK5yRgVrj/B6wUQJB+hJPwAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Code by jollysoul\n",
    " \n",
    "import random\n",
    "import numpy as np\n",
    "from matplotlib import pyplot as plt\n",
    "import matplotlib.cm as cm\n",
    " \n",
    "num_rows = int(input(\"Rows: \")) # number of rows\n",
    "num_cols = int(input(\"Columns: \")) # number of columns\n",
    " \n",
    "# The array M is going to hold the array information for each cell.\n",
    "# The first four coordinates tell if walls exist on those sides \n",
    "# and the fifth indicates if the cell has been visited in the search.\n",
    "# M(LEFT, UP, RIGHT, DOWN, CHECK_IF_VISITED)\n",
    "M = np.zeros((num_rows,num_cols,5), dtype=np.uint8)\n",
    " \n",
    "# The array image is going to be the output image to display\n",
    "image = np.zeros((num_rows*10,num_cols*10), dtype=np.uint8)\n",
    " \n",
    "# Set starting row and column\n",
    "r = 0\n",
    "c = 0\n",
    "history = [(r,c)] # The history is the stack of visited locations\n",
    " \n",
    "# Trace a path though the cells of the maze and open walls along the path.\n",
    "# We do this with a while loop, repeating the loop until there is no history, \n",
    "# which would mean we backtracked to the initial start.\n",
    "while history: \n",
    "    M[r,c,4] = 1 # designate this location as visited\n",
    "    # check if the adjacent cells are valid for moving to\n",
    "    check = []\n",
    "    if c > 0 and M[r,c-1,4] == 0:\n",
    "        check.append('L')  \n",
    "    if r > 0 and M[r-1,c,4] == 0:\n",
    "        check.append('U')\n",
    "    if c < num_cols-1 and M[r,c+1,4] == 0:\n",
    "        check.append('R')\n",
    "    if r < num_rows-1 and M[r+1,c,4] == 0:\n",
    "        check.append('D')    \n",
    "    \n",
    "    if len(check): # If there is a valid cell to move to.\n",
    "        # Mark the walls between cells as open if we move\n",
    "        history.append([r,c])\n",
    "        move_direction = random.choice(check)\n",
    "        if move_direction == 'L':\n",
    "            M[r,c,0] = 1\n",
    "            c = c-1\n",
    "            M[r,c,2] = 1\n",
    "        if move_direction == 'U':\n",
    "            M[r,c,1] = 1\n",
    "            r = r-1\n",
    "            M[r,c,3] = 1\n",
    "        if move_direction == 'R':\n",
    "            M[r,c,2] = 1\n",
    "            c = c+1\n",
    "            M[r,c,0] = 1\n",
    "        if move_direction == 'D':\n",
    "            M[r,c,3] = 1\n",
    "            r = r+1\n",
    "            M[r,c,1] = 1\n",
    "    else: # If there are no valid cells to move to.\n",
    "    # retrace one step back in history if no move is possible\n",
    "        r,c = history.pop()\n",
    "    \n",
    "         \n",
    "# Open the walls at the start and finish\n",
    "M[0,0,0] = 1\n",
    "M[num_rows-1,num_cols-1,2] = 1\n",
    "    \n",
    "# Generate the image for display\n",
    "for row in range(0,num_rows):\n",
    "    for col in range(0,num_cols):\n",
    "        cell_data = M[row,col]\n",
    "        for i in range(10*row+2,10*row+8):\n",
    "            image[i,range(10*col+2,10*col+8)] = 255\n",
    "        if cell_data[0] == 1: \n",
    "            image[range(10*row+2,10*row+8),10*col] = 255\n",
    "            image[range(10*row+2,10*row+8),10*col+1] = 255\n",
    "        if cell_data[1] == 1: \n",
    "            image[10*row,range(10*col+2,10*col+8)] = 255\n",
    "            image[10*row+1,range(10*col+2,10*col+8)] = 255\n",
    "        if cell_data[2] == 1: \n",
    "            image[range(10*row+2,10*row+8),10*col+9] = 255\n",
    "            image[range(10*row+2,10*row+8),10*col+8] = 255\n",
    "        if cell_data[3] == 1: \n",
    "            image[10*row+9,range(10*col+2,10*col+8)] = 255\n",
    "            image[10*row+8,range(10*col+2,10*col+8)] = 255\n",
    "        \n",
    " \n",
    "# Display the image\n",
    "plt.imshow(image, cmap = cm.Greys_r, interpolation='none')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f84559c9",
   "metadata": {},
   "source": [
    "我们可以维护一个迷宫单元格的列表，而不是边的列表。在这个迷宫单元格列表里面存放了未访问的单元格，我们在单元格列表中随机挑选一个单元格，如果这个单元格有多面墙联系着已存在的迷宫通路，我们就随机选择一面墙打通。这会比基于边的版本分支稍微多一点。\n",
    "\n",
    "相对于深度优先的算法，Prim随机算法不是优先选择最近选中的单元格，而是随机的从所有的列表中的单元格进行选择，新加入的单元格和旧加入的单元格同样概率会被选择，新加入的单元格没有有优先权。因此其分支更多，生成的迷宫更复杂，难度更大，也更自然。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "7ef2364d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Rows: 20\n",
      "Columns: 20\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAQEAAAD8CAYAAAB3lxGOAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAARe0lEQVR4nO3db6wc1XnH8e+vpiA1RYop4DpAaoNMJEDVbWORFwhE2iY4UVpDJVKjKrISFIOEX1TqiwCVGpS+QSkEVWqLZBQLIxWMpYpgRSTg8CKoLyjYCSL8iYMBBy627ICbkjRSkM3TFztXLNd7fXd35syc2fP7SNbdPXd25szM5eHMOWfPo4jAzMr1O11XwMy65SBgVjgHAbPCOQiYFc5BwKxwDgJmhUsWBCRtkLRf0gFJt6Y6jpnVoxTzBCStAH4GfAaYB54FboiIlxo/mJnVkqolcDlwICJei4j3gJ3AxkTHMrMaTku03/OAN4fezwOfWmpjSZ62aJbe2xFxzuLCVEFAI8o+9B+6pC3AlkTHN7OT/XxUYaogMA9cMPT+fODQ8AYRsQ3YBrB+/frYu3dvoqrMDunDsbWp/pxU++1bHca1uK7Qfn0nuV6j6jssVZ/As8A6SWslnQ5sAnYnOpaZ1ZCkJRARxyVtBR4HVgDbI+LFFMcys3pSPQ4QEY8Bj6Xav5k1wzMGzQrnIGBWOAcBs8IlmTY8cSWqyUJ1hjmaslQdJhkWqrvtuFJdrxz228S2bd2HVPtNcL32RcT6xb93S8CscA4CZoVzEDArXLJ5Ak1L1XfRVl/DUlKdV1t9PU0dp+u+qUmOn0N/S5PXyy0Bs8I5CJgVzkHArHAOAmaFcxAwK5yDgFnhshoibGqIpM4QTqohwybOreup06OkqlOqOuRwf3M7nlsCZoVzEDArnIOAWeGm7hOQdAHwAPCHwPvAtoj4F0l3AF8FflFtenu11NiyupiCWudrqanqlHIfo6SartrWCsJtf/17EqmubZN9JnU6Bo8Dfx8RP5J0JrBP0p7qd/dExF019m1mLZk6CETEYeBw9fpXkl5mkHnIzHqkkT4BSWuAPwH+uyraKul5SdslrWziGGaWRu0gIOn3gf8E/i4i3gXuBS4C5hi0FO5e4nNbJO2V5NRDZh2qtcagpN8Fvgs8HhHfGvH7NcB3I+KyZfaz7BqDqbS1Xl3X35c/lb6lN+vTPcshvVqyNQY12PO3gZeHA4Ck1UObXQe8MO0xzCy9OqMDVwBfAn4i6bmq7HbgBklzDLIQHwRuGneHOUwbnkTX01WbWo12EjlOyW5bjlOP69zfOqMD/8XoFOROPWbWI54xaFY4BwGzwmX1VeIcV2KdZp85TEFtSxf9EuNKNQ031decu/oKt1sCZoVzEDArnIOAWeEcBMwK5yBgVrisRgea0vcFOVP0onc9u3HS/eYwI7RtXc3GdEvArHAOAmaFcxAwK5yDgFnhetMx2Na0zpxXBXYduj3OgrqLlYyrqSnZy9XBLQGzwjkImBXOQcCscA4CZoVzEDArXK3RAUkHgV8BJ4DjEbFe0lnAw8AaBguNfjEi/mfM/Y197LanlaZavjrHhTtT9UrncM/sZE20BD4dEXND65nfCjwZEeuAJ6v3ZpapFI8DG4Ed1esdwLUJjmFmDakbBAJ4QtI+SVuqslVVstKFpKXnjvqg05CZ5aHujMErIuKQpHOBPZJ+Ou4HI2IbsA0+SENmZu2rFQQi4lD186ikR4DLgSOSVkfE4Sol2dEJ9lenOlPtp+vOo1RTXrte6XdSXa8QPYlUa0Ok2nY5dXIRfkTSmQuvgc8yyDu4G9hcbbYZeLRuJc0snTotgVXAI1VUPA14MCK+L+lZYJekG4E3gOvrV9PMUqmVmryxSjg1eeO6Tguesg5dy+H+TiJZanIzmw0OAmaFy2pRkS6mwbZVhxTHy2G146auV4rr0Nb07Uk+n+Mqym4JmBXOQcCscA4CZoVzEDArXFYdgzmMObc93tu3zr2+7TfF8VNJtUq2Vxs2s1NyEDArnIOAWeEcBMwK5yBgVrisRgcm0aee5y6O1/f9tn3P6u5j3OnInjZsZtlxEDArnIOAWeF60yfQpxmCqZ4vU+2jra8zp9LE14Nz6Dfq6lpOHQQkfYJBurEFFwL/CHwU+Crwi6r89oh4bNrjmFlajawxKGkF8BbwKeDLwK8j4q4JPt/ZGoMpzPJ6hH1auzDVta1zfzteRzPpGoN/DrwaET9vaH9m1pKmgsAm4KGh91slPS9pu6SVoz7gNGRmeaj9OCDpdOAQcGlEHJG0CnibQZ7CfwJWR8RXltmHHwfG2DYVPw5Mxo8DJ/sc8KOIOAIQEUci4kREvA/cxyA1mZllqokhwhsYehRYyENYvb2OQWqy2lINY7U1VXOS43S9aEbXdU25366P19SwZZP1rRUEJP0e8BngpqHib0qaY/A4cHDR78wsM3WzEv8G+INFZV+qVSMza5WnDZsVrjfThhdr6nlpVkYkFuvbNcjxK7d9mo7shUbNbGoOAmaFcxAwK5yDgFnhHATMCucgYFa43g4RNqVPw03j7rPp40xbhxy+PNO1rlYQnoRbAmaFcxAwK5yDgFnhZrJPYJJnz65XG071XJ8q130OUtQvh9WsnYHIzDrhIGBWOAcBs8I5CJgVzkHArHDLBoEqd8BRSS8MlZ0laY+kV6qfK4d+d5ukA5L2S7omVcXNrBnL5h2QdBXwa+CBiLisKvsmcCwi7pR0K7AyIr4m6RIGKw9fDnwM+AFwcUScWOYYy+YdyHG14SbWu+962nLdOvRtv33S1JTs2nkHIuIp4Nii4o3Ajur1DuDaofKdEfHbiHgdOIDzDphlbdo+gVULuQWqn+dW5ecBbw5tN1+VmVmmmp4xOKqdNrKdImkLsKXh45vZhKYNAkcWMg1JWg0crcrngQuGtjufQZ7Ck0TENmAbfNAncCo5rNqaQqrj5TB1uc5xmthvqpyQbeY4bMO0jwO7gc3V683Ao0PlmySdIWktsA54pl4VzSylZVsCkh4CrgbOljQPfB24E9gl6UbgDeB6gIh4UdIu4CXgOHDLciMDZtat2qnJG6lEw6nJu0613bd046n223Ud+v44kM0QoZnNNgcBs8I5CJgVrjcrC9UZPpnks20n8mxrWCjVcXK+tm0a99xyXGnILQGzwjkImBXOQcCscL3pE2hreu2sTBueZeNes1SrTuewMnGT3BIwK5yDgFnhHATMCucgYFY4BwGzwjkImBWuN0OEXa8wm8O028VmeUXeJr5G2+Y1yKEO03JLwKxwDgJmhXMQMCvcOGsMbge+ABwdykD0z8BfAu8BrwJfjohfSloDvAzsrz7+dETcnKLibS9rleoroDnsdxJdT7Ouq+2vf+dwfZar7zgtgfuBDYvK9gCXRcQfAz8Dbhv63asRMVf9SxIAzKw5U6Uhi4gnIuJ49fZpBvkFzKyHmugT+ArwvaH3ayX9WNIPJV3ZwP7NLKFa8wQk/QOD/AL/URUdBj4eEe9I+iTwHUmXRsS7Iz7rNGRmGZi6JSBpM4MOw7+Nqvejykb8TvV6H4NOw4tHfT4itkXE+lHroJtZe6YKApI2AF8D/ioifjNUfo6kFdXrCxmkIXutiYqaWRrTpiG7DTgD2FMNPywMBV4FfEPSceAEcHNEHBu540x0Pa2zrVWUU00xTnX92l6Vt+4+UlyHtqaF9yYNWQspmpLqem55DtdgEqnq2/V9mESCa+A0ZGZ2MgcBs8L15qvEbT22zMpqw7M2tXXYuPVtc/p219mo6jw6uCVgVjgHAbPCOQiYFc5BwKxwDgJmhctqdCDHxTyb3Me4xp3QkkOu+77NRGz7eH24Bm4JmBXOQcCscA4CZoVzEDArXFYdg22vIDyJHKb3TqJOp2FT55rDdORx9W1aepN/N24JmBXOQcCscA4CZoVzEDAr3LJBQNJ2SUclvTBUdoektyQ9V/37/NDvbpN0QNJ+SdekqriZNWOc0YH7gX8FHlhUfk9E3DVcIOkSYBNwKfAx4AeSLo6IEw3U9UNSLbLZpzXoTqXvU4xzWGOwiW0n0dXf2FRpyE5hI7Czyj/wOnAAuLxG/cwssTp9AlslPV89Lqysys4D3hzaZr4qM7NMTRsE7gUuAuYYpB67uyof1Z4Z2U6StEXSXkl7p6yDmTVgqiAQEUci4kREvA/cxwdN/nnggqFNzwcOLbEPpyEzy8BU04YlrY6Iw9Xb64CFkYPdwIOSvsWgY3Ad8EztWo6Qw5TUHOqQQu7nlWK14VQmuZZddd5Om4bsaklzDJr6B4GbACLiRUm7gJcYZCu+JcXIgJk1ZybTkE147LH2m2pYaBJtpWLr4m8iRR1SDfv1+G/BacjM7GQOAmaFcxAwK1xWi4pMIodce03Uoa3ny6Z6k3Pocc9xSvS4x8uxb8YtAbPCOQiYFc5BwKxwDgJmhetNx2COnT99Wnugqe/n59DJOq4c/2aa0uR9cEvArHAOAmaFcxAwK5yDgFnhHATMCpfV6MCs9lJPut+ce6pTrPRbV6q/mxT3IdX07TrX1i0Bs8I5CJgVzkHArHDjrDG4HfgCcDQiLqvKHgY+UW3yUeCXETEnaQ3wMrC/+t3TEXHzuJVp6pkx1eKOKfaZw1JVfVgMc5o65NhXkCqzUh1TpSGLiL9ZeC3pbuB/h7Z/NSLmGqqfmSW2bBCIiKeq/8OfRIPQ9UXgzxqul5m1pG6fwJXAkYh4ZahsraQfS/qhpCtr7t/MEqs7T+AG4KGh94eBj0fEO5I+CXxH0qUR8e7iD0raAmypeXwzq2nqloCk04C/Bh5eKKuyEb9Tvd4HvApcPOrzTkNmloc6jwN/Afw0IuYXCiSdI2lF9fpCBmnIXqtXRTNLaao0ZBHxbWATH34UALgK+Iak48AJ4OaIONZERdsalkm1UEiKIai2szCN2rbOcZratgl1j9f1VO9a96WvacgmkXMQ6Pq86m7bN12vBtXxfXAaMjM7mYOAWeGy+irxJNpusqaaVprDNNxJ1Klv29l32uzHaUJX07fdEjArnIOAWeEcBMwK5yBgVjgHAbPCOQiYFa63Q4Rta3MV4hQr5zQlxVDeOMc5lVTDrE3UoQ8zN90SMCucg4BZ4RwEzArXmz6Brr/tmOP03q6vyXL6tOrzJPo2fXvBUvV2S8CscA4CZoVzEDArnIOAWeEcBMwK5yBgVrishgjbnJo7C3XoU11nXYp71ta1dUvArHC5tATeBv6v+jlrzmY2zwtm99xm9bz+aFRhFnkHACTtncWUZLN6XjC75zar57UUPw6YFc5BwKxwOQWBbV1XIJFZPS+Y3XOb1fMaKZs+ATPrRk4tATPrQOdBQNIGSfslHZB0a9f1qUvSQUk/kfScpL1V2VmS9kh6pfq5sut6LkfSdklHJb0wVLbkeUi6rbqH+yVd002tx7PEud0h6a3qvj0n6fNDv+vNuU2j0yAgaQXwb8DngEuAGyRd0mWdGvLpiJgbGma6FXgyItYBT1bvc3c/sGFR2cjzqO7ZJuDS6jP/Xt3bXN3PyecGcE913+Yi4jHo5blNrOuWwOXAgYh4LSLeA3YCGzuuUwobgR3V6x3Atd1VZTwR8RRwbFHxUuexEdgZEb+NiNeBAwzubZaWOLel9OrcptF1EDgPeHPo/XxV1mcBPCFpn6QtVdmqiDgMUP08t7Pa1bPUeczKfdwq6fnqcWHhUWdWzm1JXQeBUd+Q6PtwxRUR8acMHnFukXRV1xVqwSzcx3uBi4A54DBwd1U+C+d2Sl0HgXnggqH35wOHOqpLIyLiUPXzKPAIg6bjEUmrAaqfR7urYS1LnUfv72NEHImIExHxPnAfHzT5e39uy+k6CDwLrJO0VtLpDDpgdndcp6lJ+oikMxdeA58FXmBwTpurzTYDj3ZTw9qWOo/dwCZJZ0haC6wDnumgflNbCG6V6xjcN5iBc1tOp98ijIjjkrYCjwMrgO0R8WKXdappFfBI9T3w04AHI+L7kp4Fdkm6EXgDuL7DOo5F0kPA1cDZkuaBrwN3MuI8IuJFSbuAl4DjwC0RcaKTio9hiXO7WtIcg6b+QeAm6N+5TcMzBs0K1/XjgJl1zEHArHAOAmaFcxAwK5yDgFnhHATMCucgYFY4BwGzwv0/KywBwUQPv4AAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import random\n",
    "import numpy as np\n",
    "from matplotlib import pyplot as plt\n",
    "import matplotlib.cm as cm\n",
    " \n",
    "num_rows = int(input(\"Rows: \")) # number of rows\n",
    "num_cols = int(input(\"Columns: \")) # number of columns\n",
    " \n",
    "# The array M is going to hold the array information for each cell.\n",
    "# The first four coordinates tell if walls exist on those sides \n",
    "# and the fifth indicates if the cell has been visited in the search.\n",
    "# M(LEFT, UP, RIGHT, DOWN, CHECK_IF_VISITED)\n",
    "M = np.zeros((num_rows,num_cols,5), dtype=np.uint8)\n",
    " \n",
    "# The array image is going to be the output image to display\n",
    "image = np.zeros((num_rows*10,num_cols*10), dtype=np.uint8)\n",
    " \n",
    "# Set starting row and column\n",
    "r = 0\n",
    "c = 0\n",
    "history = [(r,c)] # The history is the stack of visited locations\n",
    " \n",
    "# Trace a path though the cells of the maze and open walls along the path.\n",
    "# We do this with a while loop, repeating the loop until there is no history, \n",
    "# which would mean we backtracked to the initial start.\n",
    "while history: \n",
    "\t#random choose a candidata cell from the cell set histroy\n",
    "\tr,c = random.choice(history)\n",
    "\tM[r,c,4] = 1 # designate this location as visited\n",
    "\thistory.remove((r,c))\n",
    "\tcheck = []\n",
    "\t# If the randomly chosen cell has multiple edges \n",
    "    # that connect it to the existing maze, \n",
    "\tif c > 0:\n",
    "\t\tif M[r,c-1,4] == 1:\n",
    "\t\t\tcheck.append('L')\n",
    "\t\telif M[r,c-1,4] == 0:\n",
    "\t\t\thistory.append((r,c-1))\n",
    "\t\t\tM[r,c-1,4] = 2\n",
    "\tif r > 0:\n",
    "\t\tif M[r-1,c,4] == 1: \n",
    "\t\t\tcheck.append('U') \n",
    "\t\telif M[r-1,c,4] == 0:\n",
    "\t\t\thistory.append((r-1,c))\n",
    "\t\t\tM[r-1,c,4] = 2\n",
    "\tif c < num_cols-1:\n",
    "\t\tif M[r,c+1,4] == 1: \n",
    "\t\t\tcheck.append('R')\n",
    "\t\telif M[r,c+1,4] == 0:\n",
    "\t\t\thistory.append((r,c+1))\n",
    "\t\t\tM[r,c+1,4] = 2 \n",
    "\tif r < num_rows-1:\n",
    "\t\tif M[r+1,c,4] == 1: \n",
    "\t\t\tcheck.append('D') \n",
    "\t\telif  M[r+1,c,4] == 0:\n",
    "\t\t\thistory.append((r+1,c))\n",
    "\t\t\tM[r+1,c,4] = 2\n",
    " \n",
    "    # select one of these edges at random.\n",
    "\tif len(check):\n",
    "\t\tmove_direction = random.choice(check)\n",
    "\t\tif move_direction == 'L':\n",
    "\t\t\tM[r,c,0] = 1\n",
    "\t\t\tc = c-1\n",
    "\t\t\tM[r,c,2] = 1\n",
    "\t\tif move_direction == 'U':\n",
    "\t\t\tM[r,c,1] = 1\n",
    "\t\t\tr = r-1\n",
    "\t\t\tM[r,c,3] = 1\n",
    "\t\tif move_direction == 'R':\n",
    "\t\t\tM[r,c,2] = 1\n",
    "\t\t\tc = c+1\n",
    "\t\t\tM[r,c,0] = 1\n",
    "\t\tif move_direction == 'D':\n",
    "\t\t\tM[r,c,3] = 1\n",
    "\t\t\tr = r+1\n",
    "\t\t\tM[r,c,1] = 1\n",
    "         \n",
    "# Open the walls at the start and finish\n",
    "M[0,0,0] = 1\n",
    "M[num_rows-1,num_cols-1,2] = 1\n",
    "    \n",
    "# Generate the image for display\n",
    "for row in range(0,num_rows):\n",
    "    for col in range(0,num_cols):\n",
    "        cell_data = M[row,col]\n",
    "        for i in range(10*row+2,10*row+8):\n",
    "            image[i,range(10*col+2,10*col+8)] = 255\n",
    "        if cell_data[0] == 1: \n",
    "            image[range(10*row+2,10*row+8),10*col] = 255\n",
    "            image[range(10*row+2,10*row+8),10*col+1] = 255\n",
    "        if cell_data[1] == 1: \n",
    "            image[10*row,range(10*col+2,10*col+8)] = 255\n",
    "            image[10*row+1,range(10*col+2,10*col+8)] = 255\n",
    "        if cell_data[2] == 1: \n",
    "            image[range(10*row+2,10*row+8),10*col+9] = 255\n",
    "            image[range(10*row+2,10*row+8),10*col+8] = 255\n",
    "        if cell_data[3] == 1: \n",
    "            image[10*row+9,range(10*col+2,10*col+8)] = 255\n",
    "            image[10*row+8,range(10*col+2,10*col+8)] = 255\n",
    "        \n",
    " \n",
    "# Display the image\n",
    "plt.imshow(image, cmap = cm.Greys_r, interpolation='none')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4571c9a9",
   "metadata": {},
   "source": [
    "递归分割法生成的迷宫较为简单，有点像四叉树，直路多且不扭曲。通俗的说，就是把空间用十字分成四个子空间，然后在三面墙上挖洞（为了确保连通），之后对每个子空间继续做这件事直到空间不足以继续分割为止。此算法十分高效。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "b5b1453c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Rows: 20\n",
      "Columns: 20\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAQEAAAD8CAYAAAB3lxGOAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAQh0lEQVR4nO3db6wc1XnH8e+vpiA1RYop4Drg1AaZSBhVt43lvEAg0jbBidIaKpEYRZGVoBgk/KJSXwRTqUHpG5RCUKW2SEaxMFLBWKoIVkQCDi+C+oJiO0GEP3GwwYGLLd+Am5I0UpDN0xc7NyyXvb67O3N2zuz5fSR0d8/Ozjxnxnly5pyzcxQRmFm5fq/tAMysXU4CZoVzEjArnJOAWeGcBMwK5yRgVrhkSUDSRkmHJB2WdFuq45hZPUoxT0DSMuBnwKeAWWA/cGNEvNj4wcysllQtgQ3A4Yh4JSLeAXYDmxIdy8xqOCvRfi8CXu97Pwt8YrGNJXnaoll6b0bEBQsLUyUBDSh73//QJW0FtiY6vpl90M8HFaZKArPAqr73FwPH+jeIiB3ADoD169fHgQMHEoVyZtL785V/S9GOFNdh4T67tt8z7bPOtgul6hPYD6yVtEbS2cBmYG+iY5lZDUlaAhFxStI24HFgGbAzIl5IcSwzqyfV7QAR8RjwWKr9m1kzPGPQrHBOAmaFcxIwK1ySacMjB5F4slCd4ZNx9ltnn10zqWGscWIYZSiv7jUbdr+pzteQ2x6MiPULP3dLwKxwTgJmhXMSMCtcsnkC42jqHihVDJPcxyRN6t59FE3EMMp1GGXbHPp8mvw35paAWeGcBMwK5yRgVjgnAbPCOQmYFc5JwKxwWQ0RNiXFEM6kppU2sc+6+50Wqa5ZHU1dlyaHzN0SMCuck4BZ4ZwEzAo3dp+ApFXAA8AfA+8COyLiXyTdAXwV+EW16e3Vo8ZqqXPPM+mfsKbaxyixdm0a7ChS/VtIsY8uXIc6HYOngL+PiB9JOhc4KGlf9dk9EXFX/fDMLLWxk0BEHAeOV69/JekleisPmVmHNNInIGk18GfAf1dF2yQ9J2mnpOVNHMPM0qidBCT9IfCfwN9FxNvAvcClwAy9lsLdi3xvq6QDktpZesjMgJrPGJT0+8B3gccj4lsDPl8NfDcirlhiPwHNTc5I8ay2VEtPjSLVMxUyew7ektsOK4drNorOPWNQvT1/G3ipPwFIWtm32fXA8+Mew8zSqzM6cCXwJeAnkp6tym4HbpQ0Q28V4qPAzTWO8TtdWjg0h+mqXTpfg6QaLmt7ODTH61BndOC/GLwEuZceM+sQzxg0K5yTgFnhpvKnxG3fd3Vhqmi/ts9XLjGUyi0Bs8I5CZgVzknArHBOAmaFcxIwK9xUjg7U6XEf5bttP+SjS7E2GUMOIyrTxC0Bs8I5CZgVzknArHBOAmaFm8qOwS5NQa3TCZdDPduIIYd6p9BWh6dbAmaFcxIwK5yTgFnhnATMCuckYFa4WqMDko4CvwJOA6ciYr2k84CHgdX0HjT6+Yj4nyH3N8qxR4x2+uRwDlLF4GnDk9NES+CTETHT9zzz24AnI2It8GT13swyleJ2YBOwq3q9C7guwTHMrCF1k0AAT0g6KGlrVbaiWqx0ftHSCwd90cuQmeWh7ozBKyPimKQLgX2SfjrsFyNiB7AD3luGzMwmr1YSiIhj1d85SY8AG4ATklZGxPFqSbK5EfZXJ5yxeA289tcMHFXO57KOzk0blvQhSefOvwY+TW/dwb3AlmqzLcCjdYM0s3TqtARWAI9U2ess4MGI+L6k/cAeSTcBrwE31A/TzFKptTR5Y0E0vDT5iMd+33vfDuR/OzCtOrc0uZlNBycBs8J15qEibU8VrXv8FPHnPrU2hxgmZbFr0YVz4JaAWeGcBMwK5yRgVjgnAbPCdaZjsO3x6LpLc006/rbPVy4xpJDDkm5NckvArHBOAmaFcxIwK5yTgFnhnATMCteZ0YFJ9Zymmv7ZRI9y2+dgkC5Mi21TF86PWwJmhXMSMCuck4BZ4TrTJ5Bq9tmw92w5zBhs+xwMMq2zApvShfMzdhKQ9DF6y43NuwT4R+DDwFeBX1Tlt0fEY+Mex8zSauQZg5KWAW8AnwC+DPw6Iu4a4ft+xmCL/IzB7snxGYN/CRyJiJ83tD8zm5CmksBm4KG+99skPSdpp6Tlg77gZcjM8lD7dkDS2cAxYF1EnJC0AniT3jqF/wSsjIivLLEP3w60yLcD3ZPb7cBngB9FxIkqmBMRcToi3gXuo7c0mZllqokhwhvpuxWYX4ewens9vaXJapvU9MtJT/PMcVrpKDHlEH/b06xHkWMrq1YSkPQHwKeAm/uKvylpht7twNEFn5lZZuquSvwb4I8WlH2pVkRmNlGeNmxWuOKnDbdtWuuVg0lOs+7ydXRLwKxwTgJmhXMSMCuck4BZ4ZwEzArnJGBWuKyGCHOc5lmiUaa2Wk+K8zKp6dtuCZgVzknArHBOAmaFy6pPoMtTLychhwd6+BqNJocHtizVX+CWgFnhnATMCuckYFY4JwGzwjkJmBVuySRQrR0wJ+n5vrLzJO2T9HL1d3nfZ9slHZZ0SNK1qQI3s2Ysue6ApKuBXwMPRMQVVdk3gZMRcaek24DlEfE1SZfTe/LwBuAjwA+AyyLi9BLHWHLdgZKmq07r03OtuSHCia47EBFPAScXFG8CdlWvdwHX9ZXvjojfRsSrwGG87oBZ1sbtE1gxv7ZA9ffCqvwi4PW+7WarMjPLVNMzBge1/wa2UyRtBbY2fHwzG9G4SeDE/EpDklYCc1X5LLCqb7uL6a1T+AERsQPYAe/1CZzJpJ4cm/O02JxjG6Rr8abQhX6RcW8H9gJbqtdbgEf7yjdLOkfSGmAt8Ey9EM0spSVbApIeAq4Bzpc0C3wduBPYI+km4DXgBoCIeEHSHuBF4BRw61IjA2bWrtpLkzcSxJQtTW42bwLDfqNsm2xpcjPrMCcBs8I5CZgVLqsnC+UwnJJDDMNOG/aUXWuCWwJmhXMSMCuck4BZ4bLqE2jjSazTyucnD13om3FLwKxwTgJmhXMSMCuck4BZ4ZwEzArnJGBWuKyGCEfRhaGXfqM8QbiJ4b2unZ+u6/KQrFsCZoVzEjArnJOAWeGGecbgTuBzwFzfCkT/DPw18A5wBPhyRPxS0mrgJeBQ9fWnI+KWJgLt8j1XG3y+0knV39LWNRumJXA/sHFB2T7gioj4U+BnwPa+z45ExEz1XyMJwMzSGWsZsoh4IiJOVW+fpre+gJl1UBN9Al8Bvtf3fo2kH0v6oaSrGti/mSVUa56ApH+gt77Af1RFx4GPRsRbkj4OfEfSuoh4e8B3vQyZWQbGbglI2kKvw/CLUfVoVKsRv1W9Pkiv0/CyQd+PiB0RsX7Qc9DNbHLGSgKSNgJfA/4mIn7TV36BpGXV60voLUP2ShOBmlka4y5Dth04B9hXDZfMDwVeDXxD0ingNHBLRJwcuOPBxxq5Al0xyvBPE+dhms9lHaNM3560tp6eldUyZNMsxT8+P3J8dKmSQIrHxHsZMjObCCcBs8Jl9VPiHG5NJm1SfQUlnttRTLrPJiduCZgVzknArHBOAmaFcxIwK5yTgFnhshodmLZe19SaOl8+7/V1+Ry6JWBWOCcBs8I5CZgVzknArHBZdQx6ams7fN7T6UKHoVsCZoVzEjArnJOAWeGcBMwKt2QSkLRT0pyk5/vK7pD0hqRnq/8+2/fZdkmHJR2SdG2qwM2sGcOMDtwP/CvwwILyeyLirv4CSZcDm4F1wEeAH0i6LCJODxNMG2u8daH31iylsZYhO4NNwO5q/YFXgcPAhhrxmVlidfoEtkl6rrpdWF6VXQS83rfNbFVmZpkaNwncC1wKzNBbeuzuqnxQ23pgW1zSVkkHJB0YMwYza8BYSSAiTkTE6Yh4F7iP95r8s8Cqvk0vBo4tsg8vQ2aWgbGmDUtaGRHHq7fXA/MjB3uBByV9i17H4FrgmWH328b01banzA7qmGw7JmtOFzqex12G7BpJM/Sa+keBmwEi4gVJe4AX6a1WfOuwIwNm1o6sliHLIZZJc0tgunkZMjPLnpOAWeGcBMwKl9VDRbrQk9ov1TLXXTsPw/L07Ty5JWBWOCcBs8I5CZgVzknArHBZdQxO8ySZUToRcz4Po0xSqSPnczBt3BIwK5yTgFnhnATMCuckYFY4JwGzwmU1OnAmdX5mmUqqHuxh42/jZ6lLffdMUu13FKmmeg+73xxHPdwSMCuck4BZ4ZwEzAo3zDMGdwKfA+Yi4oqq7GHgY9UmHwZ+GREzklYDLwGHqs+ejohbmg56KXXuPXO4Z8shhsVMKrYmjjOp+/yuG2sZsoj4wvxrSXcD/9u3/ZGImGkoPjNLbMkkEBFPVf8P/wHqpcTPA3/RcFxmNiF1+wSuAk5ExMt9ZWsk/VjSDyVdVXP/ZpZY3XkCNwIP9b0/Dnw0It6S9HHgO5LWRcTbC78oaSuwtebxzaymsVsCks4C/hZ4eL6sWo34rer1QeAIcNmg73sZMrM81Lkd+CvgpxExO18g6QJJy6rXl9BbhuyVeiGaWUpjLUMWEd8GNvP+WwGAq4FvSDoFnAZuiYiTzYb8u7hS7Dbr4Z86sY3y3aamApd4jbqoM8uQdf3CN/FkoRzPQaprNun91r0OTfx2wMuQmVkrnATMCteZnxJP6me7k262j1KvVNOhU02d7tJDSHO4LW6LWwJmhXMSMCuck4BZ4ZwEzArnJGBWOCcBs8J1Zogwx9lyTUg1qy6Vab0OJXNLwKxwTgJmhXMSMCtcZ/oE2p7WmWp6b4rvN7WPSe43x6c+T4v5c7lYf45bAmaFcxIwK5yTgFnhnATMCuckYFY4JwGzwmU1ROgpqT1tn4e2j59LDCmkeupznfPlloBZ4XJpCbwJ/F/1d9qcz3TWC6a3btNarz8ZVJjFugMAkg5M45Jk01ovmN66TWu9FuPbAbPCOQmYFS6nJLCj7QASmdZ6wfTWbVrrNVA2fQJm1o6cWgJm1oLWk4CkjZIOSTos6ba246lL0lFJP5H0rKQDVdl5kvZJern6u7ztOJciaaekOUnP95UtWg9J26treEjSte1EPZxF6naHpDeq6/aspM/2fdaZuo2j1SQgaRnwb8BngMuBGyVd3mZMDflkRMz0DTPdBjwZEWuBJ6v3ubsf2LigbGA9qmu2GVhXfeffq2ubq/v5YN0A7qmu20xEPAadrNvI2m4JbAAOR8QrEfEOsBvY1HJMKWwCdlWvdwHXtRfKcCLiKeDkguLF6rEJ2B0Rv42IV4HD9K5tlhap22I6VbdxtJ0ELgJe73s/W5V1WQBPSDooaWtVtiIijgNUfy9sLbp6FqvHtFzHbZKeq24X5m91pqVui2o7CQz61UPXhyuujIg/p3eLc6ukq9sOaAKm4TreC1wKzADHgbur8mmo2xm1nQRmgVV97y8GjrUUSyMi4lj1dw54hF7T8YSklQDV37n2IqxlsXp0/jpGxImIOB0R7wL38V6Tv/N1W0rbSWA/sFbSGkln0+uA2dtyTGOT9CFJ586/Bj4NPE+vTluqzbYAj7YTYW2L1WMvsFnSOZLWAGuBZ1qIb2zzya1yPb3rBlNQt6W0+ivCiDglaRvwOLAM2BkRL7QZU00rgEeq33afBTwYEd+XtB/YI+km4DXghhZjHIqkh4BrgPMlzQJfB+5kQD0i4gVJe4AXgVPArRFxupXAh7BI3a6RNEOvqX8UuBm6V7dxeMagWeHavh0ws5Y5CZgVzknArHBOAmaFcxIwK5yTgFnhnATMCuckYFa4/wea2pxnU9dcCQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Code by jollysoul\n",
    " \n",
    "import random\n",
    "import numpy as np\n",
    "from matplotlib import pyplot as plt\n",
    "import matplotlib.cm as cm\n",
    " \n",
    "#这个函数将当前区域划分为四个小区域，并随机的在三个区域挖洞，\n",
    "#让四个区域彼此联通，分隔与挖洞点都是随机生成的。\n",
    "def Recursive_division(r1, r2, c1, c2, M, image):\n",
    "\tif r1 < r2 and c1 < c2:\n",
    "\t\trm = random.randint(r1, r2-1)\n",
    "\t\tcm = random.randint(c1, c2-1)\n",
    "\t\tcd1 = random.randint(c1,cm)\n",
    "\t\tcd2 = random.randint(cm+1,c2)\n",
    "\t\trd1 = random.randint(r1,rm)\n",
    "\t\trd2 = random.randint(rm+1,r2)\n",
    "\t\td = random.randint(1,4)\n",
    "\t\tif d == 1:\n",
    "\t\t\tM[rd2, cm, 2] = 1\n",
    "\t\t\tM[rd2, cm+1, 0] = 1\n",
    "\t\t\tM[rm, cd1, 3] = 1\n",
    "\t\t\tM[rm+1, cd1, 1] = 1\n",
    "\t\t\tM[rm, cd2, 3] = 1\n",
    "\t\t\tM[rm+1, cd2, 1] = 1\n",
    "\t\telif d == 2:\n",
    "\t\t\tM[rd1, cm, 2] = 1\n",
    "\t\t\tM[rd1, cm+1, 0] = 1\n",
    "\t\t\tM[rm, cd1, 3] = 1\n",
    "\t\t\tM[rm+1, cd1, 1] = 1\n",
    "\t\t\tM[rm, cd2, 3] = 1\n",
    "\t\t\tM[rm+1, cd2, 1] = 1\n",
    "\t\telif d == 3:\n",
    "\t\t\tM[rd1, cm, 2] = 1\n",
    "\t\t\tM[rd1, cm+1, 0] = 1\n",
    "\t\t\tM[rd2, cm, 2] = 1\n",
    "\t\t\tM[rd2, cm+1, 0] = 1\n",
    "\t\t\tM[rm, cd2, 3] = 1\n",
    "\t\t\tM[rm+1, cd2, 1] = 1\n",
    "\t\telif d == 4:\n",
    "\t\t\tM[rd1, cm, 2] = 1\n",
    "\t\t\tM[rd1, cm+1, 0] = 1\n",
    "\t\t\tM[rd2, cm, 2] = 1\n",
    "\t\t\tM[rd2, cm+1, 0] = 1\n",
    "\t\t\tM[rm, cd1, 3] = 1\n",
    "\t\t\tM[rm+1, cd1, 1] = 1\n",
    " \n",
    "\t\tRecursive_division(r1, rm, c1, cm, M, image)\n",
    "\t\tRecursive_division(r1, rm, cm+1, c2, M, image)\n",
    "\t\tRecursive_division(rm+1, r2, cm+1, c2, M, image)\n",
    "\t\tRecursive_division(rm+1, r2, c1, cm, M, image)\n",
    " \n",
    "\telif r1 < r2:\n",
    "\t\trm = random.randint(r1, r2-1)\n",
    "\t\tM[rm,c1,3] = 1\n",
    "\t\tM[rm+1,c1,1] = 1\n",
    "\t\tRecursive_division(r1, rm, c1, c1, M, image)\n",
    "\t\tRecursive_division(rm+1, r2, c1, c1, M, image)\n",
    "\telif c1 < c2:\n",
    "\t\tcm = random.randint(c1,c2-1)\n",
    "\t\tM[r1,cm,2] = 1\n",
    "\t\tM[r1,cm+1,0] = 1\n",
    "\t\tRecursive_division(r1, r1, c1, cm, M, image)\n",
    "\t\tRecursive_division(r1, r1, cm+1, c2, M, image)\n",
    " \n",
    " \n",
    "num_rows = int(input(\"Rows: \")) # number of rows\n",
    "num_cols = int(input(\"Columns: \")) # number of columns\n",
    "r1 = 0\n",
    "r2 = num_rows-1\n",
    "c1 = 0\n",
    "c2 = num_cols-1\n",
    " \n",
    "# The array M is going to hold the array information for each cell.\n",
    "# The first four coordinates tell if walls exist on those sides \n",
    "# and the fifth indicates if the cell has been visited in the search.\n",
    "# M(LEFT, UP, RIGHT, DOWN, CHECK_IF_VISITED)\n",
    "M = np.zeros((num_rows,num_cols,5), dtype=np.uint8)\n",
    " \n",
    "# The array image is going to be the output image to display\n",
    "image = np.zeros((num_rows*10,num_cols*10), dtype=np.uint8)\n",
    " \n",
    "Recursive_division(r1, r2, c1, c2, M, image)  \n",
    " \n",
    "# Open the walls at the start and finish\n",
    "M[0,0,0] = 1\n",
    "M[num_rows-1,num_cols-1,2] = 1\n",
    "    \n",
    "# Generate the image for display\n",
    "for row in range(0,num_rows):\n",
    "    for col in range(0,num_cols):\n",
    "        cell_data = M[row,col]\n",
    "        for i in range(10*row+2,10*row+8):\n",
    "            image[i,range(10*col+2,10*col+8)] = 255\n",
    "        if cell_data[0] == 1: \n",
    "            image[range(10*row+2,10*row+8),10*col] = 255\n",
    "            image[range(10*row+2,10*row+8),10*col+1] = 255\n",
    "        if cell_data[1] == 1: \n",
    "            image[10*row,range(10*col+2,10*col+8)] = 255\n",
    "            image[10*row+1,range(10*col+2,10*col+8)] = 255\n",
    "        if cell_data[2] == 1: \n",
    "            image[range(10*row+2,10*row+8),10*col+9] = 255\n",
    "            image[range(10*row+2,10*row+8),10*col+8] = 255\n",
    "        if cell_data[3] == 1: \n",
    "            image[10*row+9,range(10*col+2,10*col+8)] = 255\n",
    "            image[10*row+8,range(10*col+2,10*col+8)] = 255\n",
    "        \n",
    " \n",
    "# Display the image\n",
    "plt.imshow(image, cmap = cm.Greys_r, interpolation='none')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "da7aa4f9",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
